﻿#define _CRT_SECURE_NO_WARNINGS 1
//一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
//答案需要取模 1e9 + 7（1000000007），如计算初始结果为：1000000008，请返回 1。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int numWays(int n){
//	int dq[n + 1];
//	for (int i = 0; i <= n; i++)
//	{
//		if (i == 0)
//		{
//			dq[i] = 1;
//		}
//		else if (i == 1)
//		{
//			dq[i] = 1;
//		}
//		else
//		{
//			dq[i] = ((dq[i - 1] + dq[i - 2]) % 1000000007);
//		}
//	}
//	return dq[n];
//}







//
//写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
//
//F(0) = 0, F(1) = 1
//F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
//斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
//
//答案需要取模 1e9 + 7（1000000007），如计算初始结果为：1000000008，请返回 1。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int fib(int n){
//	if (n == 1)
//	{
//		return 1;
//	}
//	if (n == 0)
//	{
//		return 0;
//	}
//	int a = 1;
//	int b = 1;
//	int c = 0;
//	for (int i = 2; i<n; i++)
//	{
//		c = (a + b) % 1000000007;
//		a = b;
//		b = c;
//	}
//	return b;
//}









//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3, 4, 5, 1, 2] 为[1, 2, 3, 4, 5] 的一个旋转，该数组的最小值为1。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int minArray(int* numbers, int numbersSize){
//	for (int i = 0; i<numbersSize - 1; i++)
//	{
//		if (numbers[i]>numbers[i + 1])
//		{
//			return numbers[i + 1];
//		}
//	}
//	return numbers[0];
//}








//字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
//bool isFlipedString(char* s1, char* s2){
//	int len = strlen(s1);
//	int len2 = strlen(s2);
//	if (len == 0 && len2 == 0)
//	{
//		return 1;
//	}
//	else if (len == 0 || len2 == 0)
//	{
//		return 0;
//	}
//	char*a = (char*)malloc((len * 2 + 1)*sizeof(char));
//	strcpy(a, s1);
//	strcat(a, s1);
//	if (strstr(a, s2) != NULL)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}







//字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/compress-string-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char* compressString(char* S){
//	int count = 1;
//	int i = 0;
//	int j = 0;
//	int len = strlen(S);
//	char* a = (char*)malloc((len * 2 + 2)*sizeof(char));
//	for (i = 1; i<len + 1; i++)
//	{
//		if (S[i] == S[i - 1])
//		{
//			count++;
//		}
//		else
//		{
//			a[j++] = S[i - 1];
//			int b = sprintf(&a[j], "%d", count);
//			j += b;
//			count = 1;
//		}
//	}
//	a[j] = '\0';
//	if (strlen(a) >= len)
//	{
//		return S;
//	}
//	return a;
//}








//给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
//回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
//回文串不一定是字典当中的单词。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/palindrome-permutation-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool canPermutePalindrome(char* s){
//	int a[128] = { 0 };
//	int len = strlen(s);
//	int count = 0;
//	for (int i = 0; i<len; i++)
//	{
//		a[s[i]]++;
//	}
//	for (int i = 0; i<128; i++)
//	{
//		if (a[i] % 2 == 1)
//		{
//			count++;
//		}
//		if (count>1)
//		{
//			return false;
//		}
//	}
//	return true;
//}







//URL化。编写一种方法，将字符串中的空格全部替换为 % 20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/string-to-url-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char* replaceSpaces(char* S, int length){
//	int j = strlen(S);
//	for (int i = length - 1; i >= 0; i--)
//	{
//		if (S[i] == ' ')
//		{
//			S[--j] = '0';
//			S[--j] = '2';
//			S[--j] = '%';
//		}
//		else
//		{
//			S[--j] = S[i];
//		}
//	}
//	return S + j;
//}







//
//给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
//bool CheckPermutation(char* s1, char* s2){
//	int len1 = strlen(s1);
//	int len2 = strlen(s2);
//	if (len1 != len2)
//	{
//		return false;
//	}
//	int i = 0;
//	for (i = 0; i<len1; i++)
//	{
//		int falg = 0;
//		for (int j = 0; j<len2; j++)
//		{
//			if (s1[i] == s2[j])
//			{
//				s1[i] = '0';
//				s2[j] = '0';
//				falg = 1;
//				break;
//			}
//		}
//		if (falg == 0)
//		{
//			return false;
//		}
//	}
//	return true;
//}
//
//





//写一个函数，求两个整数之和，要求在函数体内不得使用 “ + ”、“ - ”、“*”、“ / ” 四则运算符号。
//int add(int a, int b){
//	unsigned int c = a^b;
//	unsigned int d = a&b;
//	while (d)
//	{
//		a = c;
//		b = d << 1;
//		c = a^b;
//		d = a&b;
//	}
//	return c;
//}







//0, 1, ···, n - 1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
//
//例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int lastRemaining(int n, int m){
//	int count = 0;
//	for (int i = 2; i<n + 1; i++)
//	{
//		count = (count + m) % i;
//	}
//	return count;
//}